package com.itheima.leetcode.od.b.graph;

import java.util.Arrays;
import java.util.LinkedList;

/**
 * (C卷,200分)- 最小传输时延Ⅱ（Java & JS & Python）
 * <p>
 * 题目描述
 * <p>
 * 有M*N的节点矩阵，每个节点可以向8个方向（上、下、左、右及四个斜线方向）转发数据包，每个节点转发时会消耗固定时延，连续两个相同时延可以减少一个时延值（即当有K个相同时延的节点连续转发时可以减少K- 1个时延值），
 * <p>
 * 求左上角（0，0）开始转发数据包到右下角（M-1，N- 1）并转发出的最短时延。
 * <p>
 * 输入描述
 * <p>
 * 第一行两个数字，M、N，接下来有M行，每行有N个数据，表示M* N的矩阵。
 * <p>
 * 输出描述
 * <p>
 * 最短时延值。
 * <p>
 * 用例
 * <p>
 * 输入	3 3
 * <p>
 * 0 2 2
 * <p>
 * 1 2 1
 * <p>
 * 2 2 1
 * <p>
 * 输出	3
 * 说明	无
 * <p>
 * 输入	3 3
 * <p>
 * 2 2 2
 * <p>
 * 2 2 2
 * <p>
 * 2 2 2
 * <p>
 * 输出	4
 * <p>
 * 说明	（2 + 2 + 2 -（3-1))
 * <p>
 * <p>
 * 题目解析
 * <p>
 * 本题是求两点之间的最短路径。
 * <p>
 * 对于最短路径问题，最简单的求解思路就是BFS，但是BFS只适用于处理无权图的最短路径。
 * <p>
 * 所谓无权图，即图中各顶点之间的边没有权重，或者可以理解为各相连顶点之间距离相同。
 * <p>
 * 对于有权图的最短路径求解，有多种解题思路，比如Dijkstra，Floyed，Bellma-ford，SPFA。
 * <p>
 * 本题将使用SPFA算法来求解最短路径。
 * <p>
 * 所谓SPFA算法，其实就是对无权图的BFS算法的优化。
 * <p>
 * 在无权图的BFS扩散过程中，最先碰到终点的路径 一定是 最短路径，因为这条路径从起点到终点经历的节点数最少，而无权图中，相连节点之间的距离是相同的，因此路径中节点数越少，距离就越短。
 * 在有权图中的BFS扩散过程中，最先碰到终点的路径 不一定是 最短路径，此时各节点之间的距离是不同的，因此节点数少，不能代表路径就短。
 * <p>
 * 关于SPFA算法可以参考这个视频：
 * <a href="https://www.bilibili.com/video/BV1RK4y1d7ct/?p=4&vd_source=b5105a99a0628dd906e154263279c518">SPFA算法_哔哩哔哩_bilibili</a>
 * <p>
 */
public class SPFAMinimumTransmissionDelayII {
    public static void main(String[] args) {
        /*Scanner sc = new Scanner(System.in);

        m = sc.nextInt();
        n = sc.nextInt();

        matrix = new int[m][n];
        dist = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                matrix[i][j] = sc.nextInt();
                // 最短路径矩阵初始化，假设每个点到(0,0)距离无穷大
                dist[i][j] = Integer.MAX_VALUE;
            }
        }*/

        int m = 3; // 地图矩阵行数
        int n = 3; // 地图矩阵列数

        // 地图矩阵
        int[][] matrix = Arrays.stream("0 2 2\n1 2 1\n2 2 1".split("\n"))
                .map(s -> Arrays.stream(s.split(" "))
                        .mapToInt(Integer::parseInt)
                        .toArray())
                .toArray(int[][]::new);

        int[][] dist = new int[m][n]; // 最短路径矩阵，即dist[i][j]记录的是坐标(i,j)到(0,0)的最短距离
        boolean[][] visited = new boolean[m][n];
        Arrays.stream(dist).forEach(arr -> Arrays.fill(arr, Integer.MAX_VALUE));

        System.out.println(spfa(matrix, m, n, dist, visited));
    }

    // 八个方向偏移量
    static int[][] offsets = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}, {-1, -1}, {-1, 1}, {1, -1}, {1, 1}};

    public static int spfa(int[][] matrix, int m, int n, int[][] dist, boolean[][] visited) {
        LinkedList<int[]> queue = new LinkedList<>();
        queue.add(new int[]{0, 0});
        dist[0][0] = matrix[0][0];
        visited[0][0] = true;

        while (queue.size() > 0) {
            int[] tmp = queue.removeFirst();
            int x = tmp[0];
            int y = tmp[1];

            for (int[] offset : offsets) {
                int newX = x + offset[0];
                int newY = y + offset[1];

                if (newX >= 0 && newX < m && newY >= 0 && newY < n
                        && !visited[newX][newY]) {
                    int newDist = dist[x][y] + matrix[newX][newY];

                    // 题目说：连续两个相同时延可以减少一个时延值
                    // 但是需要注意的是，应该不能产生负的时延值，比如前一个时延是0，当前时延也是0，则减少1个时延值，不应该变为-1
                    if (matrix[newX][newY] == matrix[x][y] && matrix[newX][newY] >= 1) {
                        newDist -= 1;
                    }

                    visited[newX][newY] = true;

                    dist[newX][newY] = Math.min(newDist, dist[newX][newY]);
                    queue.add(new int[]{newX, newY});
                }
            }
        }

        return dist[m - 1][n - 1];
    }
}